/*******************************************************************************************
 *      @name   CircularLinkedList.c
 *      @brief  这是单向循环链表的代码案例，主要学习单向循环链表结点的增删改查，并设计API接口
 *      @date   2024/12/26
 *      @author cecelmx@126.com 
 *      @note
 *          1.
 *          2.
 *          3.
 *          4.
 * 
 *      @version  xx.xx.xx   主版本号.次版本号.修正版本号
 * 
 *      CopyRight (c)   2024-2025   Your Name     All Right Reserved
 * 
 * ****************************************************************************************/

#include <stdio.h>
#include <stdbool.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>


//使用面向对象的思想构造链表中结点的结构 单向循环链表结点分为2部分：数据域 + 指针域 

typedef int DataType_t;  //数据域中的数据的类型，为了提高程序的可移植性，用户后期可以修改

typedef struct Node
{
    DataType_t     Data;//数据域，用于记录结点的有效数据
    struct Node  * Next;//指针域，指向直接后继结点的地址
}Node_t;



/*******************************************************************************************
 *      @name   LinkedList_Create
 *      @brief  创建单向循环链表
 *      @param  Size : 指顺序表的容量
 *      @note   单向循环链表是具有头结点，头结点类型和其他结点类型一致，头结点不存储有效数据
 *      @retval 函数调用成功，返回指向Node_t类型的指针
 *      
 * ****************************************************************************************/
Node_t * CircularLinkedList_Create(void)
{
    //1.为头结点申请堆内存，并进行错误处理
    Node_t *Pmanager = (Node_t *)calloc(1,sizeof(Node_t));

    if(NULL == Pmanager)
    {
        fprintf(stderr,"Calloc Heap Memory For Pmanager Error,errno = %d,%s\n",
                                                            errno,strerror (errno)); 
        exit(-1); //导致程序终止
    }

    //2.对头结点的指针域进行初始化（头结点的数据域是空闲的，体现循环的思想，所以应该指向自身）
    Pmanager->Next = Pmanager; 

    printf("Create Circular LinkedList Is OK\n");

    return Pmanager;
}


/*******************************************************************************************
 *      @name   LinkedList_NewNode
 *      @brief  创建新结点
 *      @param  Data : 指结点的数据域的值
 *      @note   新结点是没有插入到链表中的，为了体现循环的思想，所以新结点的指针域应该指向自身
 *      @retval 函数调用成功，返回指向Node_t类型的指针
 *      
 * ****************************************************************************************/
Node_t * CircularLinkedList_NewNode(DataType_t Data)
{
    //1.为新结点申请堆内存，并进行错误处理
    Node_t *NewNode = (Node_t *)calloc(1,sizeof(Node_t));

    if(NULL == NewNode)
    {
        fprintf(stderr,"Calloc Heap Memory For NewNode Error,errno = %d,%s\n",
                                                            errno,strerror (errno)); 
        exit(-1); //导致程序终止
    }

    //2.对新结点初始化（数据域 + 指针域）
    NewNode->Data = Data;
    NewNode->Next=  NewNode;

    return NewNode;

}

/*******************************************************************************************
 *      @name   CircularLinkedList_HeadInsert
 *      @brief  利用头插法实现结点插入
 *      @param  HeadPointer : 指的是指向头结点的头指针
 *      @param  Data        : 指的是待插入结点的数据域
 *      @note   头插法指的是把新结点作为链表的首结点，单向循环链表的尾结点的指针域指向首结点
 *      @retval 成功返回true  失败返回false
 *      
 * ****************************************************************************************/
bool CircularLinkedList_HeadInsert(Node_t *HeadPointer,DataType_t Data)
{
    //为了提高程序的可靠性，所以需要对头指针进行备份
    Node_t * p = HeadPointer;

    //1.检查参数有效性
    if(NULL == HeadPointer)
    {
        fprintf(stderr,"Insert Error,Argument Is Invaild\n"); //错误信息
        return false;
    }

    //2.创建新结点并初始化
    Node_t * NewNode = CircularLinkedList_NewNode(Data);

    //3.分为2种情况：链表为空 or 链表非空
    if(p->Next == p)
    {
        p->Next = NewNode;  //头结点的指针域指向新结点
        printf("HeadInsert NewNode Is OK\n");
        return true;
    }

    //4.指的是链表非空的情况
    NewNode->Next = p->Next;    //让新结点的指针域指向了首结点地址
    p->Next = NewNode;          //让头结点的指针域指向新结点的地址

    //5.单向循环链表需要遍历才可以找到尾结点
    p =  NewNode->Next;

    while(p->Next != NewNode->Next)
    {
        //单向循环链表的尾结点的指针域是指向首结点,可以终止循环
        p =  p->Next;
    }

    p->Next = NewNode; //让尾结点的指针域指向新的首结点

    printf("HeadInsert NewNode Is OK\n");

    return true;
}

/*******************************************************************************************
 *      @name   CircularLinkedList_TailInsert
 *      @brief  利用尾插法实现结点插入
 *      @param  HeadPointer : 指的是指向头结点的头指针
 *      @param  Data        : 指的是待插入结点的数据域
 *      @note   尾插法指的是把新结点作为链表的尾结点，并且需要让尾结点的指针域指向首结点
 *      @retval 成功返回true  失败返回false
 *      
 * ****************************************************************************************/
bool  CircularLinkedList_TailInsert(Node_t *HeadPointer,DataType_t Data)
{
    //为了提高程序的可靠性，所以需要对头指针进行备份
    Node_t * p = HeadPointer;

    //1.检查参数有效性
    if(NULL == HeadPointer)
    {
        fprintf(stderr,"Insert Error,Argument Is Invaild\n"); //错误信息
        return false;
    }

    //2.创建新结点并初始化
    Node_t * NewNode = CircularLinkedList_NewNode(Data);

    //3.分为2种情况：链表为空 or 链表非空
    if(p->Next == p)
    {
        p->Next = NewNode;  //头结点的指针域指向新结点
        printf("TailInsert NewNode Is OK\n");
        return true;
    }

    //4.备份首结点的地址，用于更新尾结点的指针域
    Node_t * p_temp = p->Next; 

    //5.指的是链表非空的情况 单向循环链表需要遍历才可以找到尾结点
    p =  p->Next;

    while(p->Next != p_temp)
    {
        //单向循环链表的尾结点的指针域是指向首结点,可以终止循环
        p =  p->Next;
    }

    p->Next = NewNode;      //让尾结点的指针域指向新结点地址
    NewNode->Next = p_temp; //尾结点的指针域是指向首结点

    printf("TailInsert NewNode Is OK\n");

    return true;
}

/*******************************************************************************************
 *      @name   CircularLinkedList_HeadDel
 *      @brief  利用头删法实现结点删除
 *      @param  HeadPointer : 指的是指向头结点的头指针
 *      @note   注意删除结点的时候要检查链表是否为空，以及确保尾结点的指针域指向首结点   
 *      @retval 成功返回true  失败返回false
 *      
 * ****************************************************************************************/
bool CircularLinkedList_HeadDel(Node_t *HeadPointer)
{
    //1.检查参数有效性
    if(NULL == HeadPointer)
    {
        fprintf(stderr,"Delete Node Error,Argument Is Invaild\n"); //错误信息
        return false;
    }

    //2.判断单向循环链表是否为空 
    if(HeadPointer->Next == HeadPointer)
    {
        fprintf(stderr,"Delete Node Error,LinkedList Is Empty\n"); //错误信息
        return false;
    }

    //需要对头结点进行备份
    Node_t * p_prev = HeadPointer;

    //需要对首结点进行备份
    Node_t * p_current = p_prev->Next; 

   
    //3.分为两种情况：只有1个结点  or  存在n个结点
    if(p_current->Next == p_current) 
    {
        p_prev->Next = p_prev;  //让头结点指针自身，表示链表已空
        p_current->Next = NULL; //防止内存泄漏
        free(p_current);        //释放结点内存

        printf("Delete Node Is OK\n");
        return true;
    }

    //4.存在n个结点,需要对单向循环链表进行遍历，找到尾结点
    
    while(p_current->Next != HeadPointer->Next)
    {    
        p_current = p_current->Next;    //当前结点的直接后继作为新的当前结点
    }

    //5.让尾结点的指针域指向新的首结点
    p_current->Next = p_current->Next->Next;

    //6.让头结点的指针域指向新的首结点
    HeadPointer->Next->Next = NULL;   //让首结点从链表断开连接,防止内存泄漏
    free(HeadPointer->Next);          //释放结点内存  

    HeadPointer->Next = p_current->Next; //让头结点的指针域指向新的首结点

    printf("Delete Node Is OK\n");

    return true;
}


/*******************************************************************************************
 *      @name   circularLinkedList_TailDel
 *      @brief  利用尾删法实现结点删除
 *      @param  HeadPointer : 指的是指向头结点的头指针
 *      @note   注意删除结点的时候要检查链表是否为空,以及确保尾结点的指针域指向首结点     
 *      @retval 成功返回true  失败返回false
 *      
 * ****************************************************************************************/
bool circularLinkedList_TailDel(Node_t *HeadPointer)  
{
    //1.检查参数有效性
    if(NULL == HeadPointer)
    {
        fprintf(stderr,"Delete Node Error,Argument Is Invaild\n"); //错误信息
        return false;
    }

    //2.判断单向循环链表是否为空 
    if(HeadPointer->Next == HeadPointer)
    {
        fprintf(stderr,"Delete Node Error,LinkedList Is Empty\n"); //错误信息
        return false;
    }

    //需要对头结点进行备份
    Node_t * p_prev = HeadPointer;

    //需要对首结点进行备份
    Node_t * p_current = p_prev->Next; 

   
    //3.分为两种情况：只有1个结点  or  存在n个结点
    if(p_current->Next == p_current) 
    {
        p_prev->Next = p_prev;  //让头结点指针自身，表示链表已空
        p_current->Next = NULL; //防止内存泄漏
        free(p_current);        //释放结点内存

        printf("Delete Node Is OK\n");
        return true;
    }
    
    //4.存在n个结点,需要对单向循环链表进行遍历，找到尾结点和尾结点的直接前驱

    while(p_current->Next != HeadPointer->Next)
    {    
        p_prev = p_current; //先备份当前结点的地址          
        p_current = p_current->Next;    //当前结点的直接后继作为新的当前结点
    }


    //5.让待删除结点的直接前驱的指针域指向首结点，并释放待删除的结点空间
    p_prev->Next = HeadPointer->Next;
    p_current->Next = NULL; //防止内存泄漏
    free(p_current);
    
    printf("Delete Node Is OK\n");
    return true;
}

/*******************************************************************************************
 *      @name   CircularLinkedList_Print
 *      @brief  遍历结点
 *      @param  HeadPointer : 指的是指向头结点的头指针
 *      @note   None
 *      @retval None
 *      
 * ****************************************************************************************/
void CircularLinkedList_Print(Node_t *HeadPointer)
{
    //为了提高程序的可靠性，所以需要对首结点进行备份
    Node_t * p = HeadPointer->Next;

    int cnt = 0;            //用于记录链表的结点数量

    //遍历链表结点
    while(p->Next != HeadPointer->Next)
    {
        cnt++;  //结点数量+1
        printf("Th %d Node Val = %d\n",cnt,p->Data); //输出当前结点的数据域

        p = p->Next; //把当前结点的直接后继作为新的当前结点
    }

    printf("Th %d Node Val = %d\n",cnt,p->Data); //输出当前结点的数据域
}

int main()
{
    //1.创建空链表
    Node_t * HeadPointer = CircularLinkedList_Create();

    //2.头插法插入结点
    CircularLinkedList_HeadInsert(HeadPointer,10);
    CircularLinkedList_HeadInsert(HeadPointer,5);
    CircularLinkedList_HeadInsert(HeadPointer,6);
    CircularLinkedList_HeadInsert(HeadPointer,1);
    CircularLinkedList_HeadInsert(HeadPointer,20);

    //3.遍历链表
    CircularLinkedList_Print(HeadPointer);      // 20 1 6 5 10

    //4.尾插法插入结点
    CircularLinkedList_TailInsert(HeadPointer,15);
    CircularLinkedList_TailInsert(HeadPointer,9);
    CircularLinkedList_TailInsert(HeadPointer,30);
    CircularLinkedList_TailInsert(HeadPointer,17);
    CircularLinkedList_TailInsert(HeadPointer,11);

    //5.遍历链表
    CircularLinkedList_Print(HeadPointer);      // 20 1 6 5 10 15 9 30 17 11

    circularLinkedList_TailDel(HeadPointer);
    circularLinkedList_TailDel(HeadPointer);

    CircularLinkedList_Print(HeadPointer);      // 20 1 6 5 10 15 9 30


}